from collections import deque
import pandas as pd

class AhoCorasickNode:
    """Aho-Corasick算法的节点类"""
    def __init__(self):
        self.goto = {}  # 转移字典
        self.fail = None  # 失败指针
        self.output = None  # 输出（存储匹配到的地址信息）

class AhoCorasick:
    """Aho-Corasick多模匹配算法实现"""
    def __init__(self):
        self.root = AhoCorasickNode()
    
    def add_pattern(self, pattern, value):
        """添加模式串及其对应的值"""
        node = self.root
        for char in pattern:
            if char not in node.goto:
                node.goto[char] = AhoCorasickNode()
            node = node.goto[char]
        node.output = (pattern, value)  # 存储模式串和对应的值
    
    def build(self):
        """构建失败指针"""
        queue = deque()
        
        # 初始化根节点的所有子节点的失败指针为根节点
        for node in self.root.goto.values():
            node.fail = self.root
            queue.append(node)
        
        # 处理其他节点的失败指针
        while queue:
            current_node = queue.popleft()
            
            for char, child in current_node.goto.items():
                fail_node = current_node.fail
                
                # 找到合适的失败节点
                while fail_node is not None and char not in fail_node.goto:
                    fail_node = fail_node.fail
                
                child.fail = fail_node.goto[char] if fail_node else self.root
                if child.fail is None:
                    child.fail = self.root
                
                queue.append(child)
    
    def search(self, text):
        """在文本中搜索所有模式串"""
        results = []
        node = self.root
        
        for char in text:
            # 沿着失败指针查找，直到找到匹配的字符或到达根节点
            while node is not None and char not in node.goto:
                node = node.fail
            
            if node is None:
                node = self.root
            else:
                node = node.goto[char]
            
            # 收集所有匹配结果
            temp = node
            while temp != self.root:
                if temp.output is not None:
                    results.append(temp.output)
                temp = temp.fail
        
        return results


  